翻訳と辞書
Words near each other
・ Non-associative algebra
・ Non-attainment area
・ Non-autonomous mechanics
・ Non-autonomous system (mathematics)
・ Non-availability approach
・ Non-B database
・ Non-bank financial institution
・ Non-bank subsidiary
・ Non-banking financial company
・ Non-belligerent
・ Non-binding arbitration
・ Non-binding opinion
・ Non-binding opinion (United Kingdom patent law)
・ Non-binding resolution
・ Non-blocking
Non-blocking algorithm
・ Non-blocking I/O (Java)
・ Non-blocking linked list
・ Non-bonding orbital
・ Non-bracelet events at the WSOP
・ Non-breaking space
・ Non-brewed condiment
・ Non-British personnel in the RAF during the Battle of Britain
・ Non-broadcast multiple-access network
・ Non-Broadcastable
・ Non-canonical books referenced in the Bible
・ Non-celiac gluten sensitivity
・ Non-cellular life
・ Non-centrifugal cane sugar
・ Non-Chalcedonianism


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Non-blocking algorithm : ウィキペディア英語版
Non-blocking algorithm

In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress.
The word "non-blocking" was traditionally used to describe telecommunications networks that could route a connection through a set of relays "without having to re-arrange existing calls", see Clos network. Also, if the telephone exchange "is not defective, it can always make the connection", see Nonblocking minimal spanning switch.
== Motivation ==

The traditional approach to multi-threaded programming is to use locks to synchronize access to shared resources. Synchronization primitives such as mutexes, semaphores, and critical sections are all mechanisms by which a programmer can ensure that certain sections of code do not execute concurrently, if doing so would corrupt shared memory structures. If one thread attempts to acquire a lock that is already held by another thread, the thread will block until the lock is free.
Blocking a thread is undesirable for many reasons. An obvious reason is that while the thread is blocked, it cannot accomplish anything: if the blocked thread had been performing a high-priority or real-time task, it would be highly undesirable to halt its progress.
Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as deadlock, livelock, and priority inversion. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for parallelism, and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.
Non-blocking algorithms are also safe for use in interrupt handlers: even though the preempted thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock.
Some people use a lock-free data structure in order to improve performance.
A lock-free data structure increases the amount of time spent in parallel execution rather than serial execution, improving performance on a multi-core processor, because access to the shared data structure does not need to be serialized to stay coherent.〔
Guillaume Marçais, and Carl Kingsford.
("A fast, lock-free approach for efficient parallel counting of occurrences of k-mers" ).
Bioinformatics (2011) 27(6): 764-770.
("Jellyfish mer counter" ).


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Non-blocking algorithm」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.